package _02_栈;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 *
 * 思路：
 * 遇到左括号的时候就入栈，遇到右括号就将栈顶元素弹出来与之比较
 * @author : zjj
 * @date : 2021/1/15 14:09
 */
public class _20_有效的括号 {


    private static Map<Character,Character> map = new HashMap<>();

    static {
        map.put('(',')');
        map.put('{','}');
        map.put('[',']');
    }
    public static void main(String[] args) {
        System.out.println(isValid3("()(((())"));
    }

    /**
     * 方法1
     * @param str 字符串
     */
    private static void isValid(String str){
        while(str.contains("()") || str.contains("[]") || str.contains("{}")){
            str = str.replace("()","");
            str = str.replace("[]","");
            str = str.replace("{}","");

        }

        System.out.println("是否是匹配的：" + str.isEmpty());
    }

    /**
     * 方法2:
     * 用栈来处理：
     * 遇到左括号就入栈，遇到右括号就出栈，并对此是否匹配
     * 直到最后判断栈是否是空
     */
    private static void isValid2(String str){
        int length = str.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            char c = str.charAt(i);
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    System.out.println("false");
                    return;
                }
                char leftChar = stack.pop();
                if(leftChar == '(' && c != '('){
                    System.out.println("false");
                    return;
                }
                if(leftChar == '{' && c != '}'){
                    System.out.println("false");
                    return;
                }
                if(leftChar == '[' && c != ']'){
                    System.out.println("false");
                    return;
                }

            }

        }
        System.out.println(stack.isEmpty());
    }

    /**
     * 方法3：对方法二改造一下  ，将匹配的字符串放入到map中 去
     *
     */
    private static boolean isValid3(String str) {
        int length = str.length();
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            char c = str.charAt(i);
            if(map.get(c) != null){
                stack.push(c);
            }else {
                if (stack.isEmpty()) {
                    return false;
                }
                char leftChar = stack.pop();
                if(map.get(leftChar) != c){
                   return false;
               }
            }

        }
        return stack.isEmpty();
    }

}

